<html>
<head>
<link rel="shortcut icon" href="./favicon.ico">
<link rel="stylesheet" type="text/css" href="./style.css">
<link rel="canonical" href="./Logarithm_of_Powers_of_Two.html">
<meta name="viewport" content="width=device-width, initial-scale=1">
<meta name="description" content="Translates a power-of-2 binary value (a one-hot bitmask) into its integer base-2 logarithm. For example:">
<title>Logarithm of Powers of Two</title>
</head>
<body>

<p class="inline bordered"><b><a href="./Logarithm_of_Powers_of_Two.v">Source</a></b></p>
<p class="inline bordered"><b><a href="./legal.html">License</a></b></p>
<p class="inline bordered"><b><a href="./index.html">Index</a></b></p>

<h1>Logarithm of Powers of Two</h1>
<p>Translates a power-of-2 binary value (a one-hot bitmask) into its integer
 base-2 logarithm. For example:</p>
<ul>
<li>log<sub>2</sub>(0001) -&gt; log<sub>2</sub>(2<sup>0</sup>) -&gt; log<sub>2</sub>(1) -&gt; 0</li>
<li>log<sub>2</sub>(0010) -&gt; log<sub>2</sub>(2<sup>1</sup>) -&gt; log<sub>2</sub>(2) -&gt; 1</li>
<li>log<sub>2</sub>(0100) -&gt; log<sub>2</sub>(2<sup>2</sup>) -&gt; log<sub>2</sub>(4) -&gt; 2</li>
<li>log<sub>2</sub>(1000) -&gt; log<sub>2</sub>(2<sup>3</sup>) -&gt; log<sub>2</sub>(8) -&gt; 3</li>
</ul>
<p>We can see the logarithm of a power-of-2 is simply the index of the single
 set bit: log<sub>2</sub>(2<sup>set_bit_index</sup>) = set_bit_index.</p>
<p>If the input is not a power-of-2 (more than one set bit), then this
 implementation will output the bitwise-OR of the logarithm of each set bit
 treated as a power-of-2, which I'm not sure has any use or meaning. To save
 hardware (we'd need a <a href="./Population_Count.html">Population Count</a> or a pair
 of <a href="./Bitmask_Isolate_Rightmost_1_Bit.html">priority bitmasks</a>), we don't signal these
 cases.
 Also, this calculation fails if no bits are set, since log<sub>2</sub>(0)
 is undefined, and we cannot output zero as that's a valid logarithm. To
 represent the undefined case, we will set an extra bit to declare the output
 undefined, via a simple NOR-reduction of the input.</p>
<p>We can't implement using a translation table, as with the
 <a href="./Address_Translator_Static.html">Static Address Translator</a>, since we
 would have to create a table capable of holding all 2<sup>WORD_WIDTH</sup>
 possible values, and that would take a <em>long</em> time to synthesize and optimize,
 as well as require a lot of system memory.
 Instead, we precalculate each possible logarithm (one per input bit) and
 gate its value based on whether the corresponding input bit is set. We then
 OR-reduce all these possible logarithms into the final answer. We can use
 this implementation method since the amount of logic scales linearly with
 WORD_WIDTH.</p>
<p>You can use this module to implement unsigned division by powers-of-2 by
 shifting right by the logarithm value. However, <em>signed</em> division by
 powers-of-2 has a complication. See <a href="./reading.html#Warren2013">Hacker's
 Delight</a>, Section 10-1, "Signed Division by
 a Known Power of 2". </p>
<p>When combined with <a href="./Bitmask_Isolate_Rightmost_1_Bit.html">Bitmask: Isolate Rightmost
 1 Bit</a>, this module forms the basis
 for the very useful Number of Trailing Zeros (ntz) function. Add a <a href="./Word_Reverser.html">Word
 Reverser</a> and you can compute Number of Leading Zeros
 (nlz).</p>

<pre>
`default_nettype none

module <a href="./Logarithm_of_Powers_of_Two.html">Logarithm_of_Powers_of_Two</a>
#(
    parameter WORD_WIDTH = 0
)
(
    input   wire    [WORD_WIDTH-1:0]    one_hot_in,
    output  wire    [WORD_WIDTH-1:0]    logarithm_out,
    output  reg                         logarithm_undefined
);

    localparam WORD_ZERO = {WORD_WIDTH{1'b0}};

    initial begin
        logarithm_undefined = 1'b0;
    end
</pre>

<p>To keep the interface clean, logarithm_out has the same WORD_WIDTH as
 one_hot_in. To calculate each possbile logarithm in parallel, we need an
 array of one output word per input bit. But we must use a flat vector here
 instead of an array since we will be passing this vector of words to
 a Word_Reducer module, and we can't pass multidimensional arrays through
 module ports in Verilog-2001. This means you will hit the Verilog vector
 width limit of about a million when WORD_WIDTH reaches about 1024, though
 simulation and synthesis will have become impractically slow long before
 then.</p>

<pre>
    localparam TOTAL_WIDTH  = WORD_WIDTH * WORD_WIDTH;
    localparam TOTAL_ZERO   = {TOTAL_WIDTH{1'b0}};

    reg [TOTAL_WIDTH-1:0] all_logarithms = TOTAL_ZERO;
</pre>

<p>Most of those logarithm output bits remain a constant zero (and so require
 no logic) since representing the value of a binary number up to
 2<sup>N</sup>-1 require at most log<sub>2</sub>(N) bits. Therefore,
 representing log<sub>2</sub>(2<sup>N</sup>-1) in binary only needs
 log<sub>2</sub>(log<sub>2</sub>(N)) bits, which is a value that grows
 <strong>very</strong> slowly. Having output bits stuck at zero will raise CAD tool
 warnings, but that's a lot less error-prone than having the enclosing logic
 calculate the required output logarithm bit width.</p>
<p>This implementation would ultimately fail if the computed logarithm needs
 more bits than a 32-bit Verilog integer. However, as explained above, that
 would require an input value exceeding 2<sup>2<sup>32</sup></sup>-1, which
 is 2<sup>32</sup> bits long. You are not likely to reach this limit.</p>
<p>So we pre-compute how many bits we will need to represent the logarithm,
 and also create some zero-padding to expand the logarithm back to
 WORD_WIDTH.</p>

<pre>
    `include "<a href="./clog2_function.html">clog2_function</a>.vh"
    localparam LOGARITHM_WIDTH = clog2(WORD_WIDTH);
    localparam PAD_WIDTH = WORD_WIDTH - LOGARITHM_WIDTH;
    localparam PAD = {PAD_WIDTH{1'b0}};
</pre>

<p>Then, for each set input bit, put its logarithm (the bit index) into the
 corresponding array word, else put zero. Note how we slice the integer
 logarithm down to the necessary bits and then pad those back up to the
 array word width.</p>

<pre>
    generate
        genvar i;
        for(i = 0; i < WORD_WIDTH; i = i + 1) begin : per_input_bit
            always @(*) begin
                all_logarithms[WORD_WIDTH*i +: WORD_WIDTH] = (one_hot_in[i] == 1'b1) ? {PAD, i[LOGARITHM_WIDTH-1:0]} : WORD_ZERO;
            end
        end
    endgenerate
</pre>

<p>Then, we OR-reduce the array of possible logarithms down to one.</p>

<pre>
    <a href="./Word_Reducer.html">Word_Reducer</a>
    #(
        .OPERATION  ("OR"),
        .WORD_WIDTH (WORD_WIDTH),
        .WORD_COUNT (WORD_WIDTH)
    )
    combine_logarithms
    (
        .words_in   (all_logarithms),
        .word_out   (logarithm_out)
    );
</pre>

<p>Finally, we detect the case where all input bits are zero and the logarithm
 is undefined.</p>

<pre>
    always @(*) begin
        logarithm_undefined = (one_hot_in == WORD_ZERO);
    end

endmodule
</pre>

<hr>
<p><a href="./index.html">Back to FPGA Design Elements</a>
<center><a href="https://fpgacpu.ca/">fpgacpu.ca</a></center>
</body>
</html>

